#include <stdio.h>
#include <stdlib.h>
#include "BinarySortTree.h"
#include "LinkQueue.h"

#define true 1
#define false 0

//创建二叉树节点
BSTNode* BST_CreateTreeNode(ElementType element)
{
    BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));//申请节点空间
    if(newNode == NULL)
    {
        printf("CreateTreeNode malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->left = newNode->right = newNode->parent = NULL;
    return newNode;
}


//初始化二叉树
int BST_Init(BSTree* tree)
{
    tree->root = NULL;
    return true;
}

//创建二叉树,返回指针
BSTree* BST_Create()
{
    BSTree* pBSTree = (BSTree*)malloc(sizeof(BSTree));
    if(pBSTree == NULL)
        return NULL;
    pBSTree->root = NULL;
    return pBSTree;
}

//从某节点开始插入:
//回调函数compare两参数的value1,value2
//value1 < value2,返回1
//value1 < value2,返回0
void BST_InsertNode(BSTNode* node, ElementType element, int(*compare)(ElementType, ElementType))
{
    if(node == NULL)
       return;

    if(compare(element, node->data))//插入元素比node->data小，找node的左子树
    {
        if(node->left != NULL)              //node节点左孩子不为空，递归比较node左孩子的左右孩子的数据
           BST_InsertNode(node->left, element, compare);
        else                                //node节点左孩子为空，element作为node->left插入
        {
            node->left = BST_CreateTreeNode(element);//创建node->left节点，保存element
            if(node->left == NULL)
            {
                printf("CreateNode error!\n");
                return;
            }
            node->left->parent = node;//将element1节点的父节点指向node
        }
    }
    else //插入元素比node->data大，找node的右子树
    {
        if(node->right != NULL)//node节点左孩子不为空，递归比较node右孩子的左右孩子的数据
           BST_InsertNode(node->right, element, compare);
        else
        {
            node->right = BST_CreateTreeNode(element);//创建node->right节点，保存element
            if(node->right == NULL)
            {
                printf("CreateNode error!\n");
                return;
            }
            node->right->parent = node;//将element1节点的父节点指向node
        }
    }
}

// 从根节点开始比较插入：
void BST_InsertElement(BSTree* tree, ElementType element, int(*func)(ElementType, ElementType))
{
    if(tree->root == NULL)//若根节点为空，直接将element插入根节点处
    {
        tree->root = BST_CreateTreeNode(element);//创建根节点
        if(tree->root == NULL)
        {
            printf("Create root error!\n");
            return;
        }
    }
    else
        BST_InsertNode(tree->root, element, func);//根节点存在，往下递归
}

//释放节点
void BST_FreeNode(BSTNode* node, DataDestroy dataDestroy)
{
    if(node == NULL)
        return;
    BST_FreeNode(node->left, dataDestroy);
    BST_FreeNode(node->right, dataDestroy);
    dataDestroy(node->data);
    free(node);
}

//销毁整颗树
void BST_FreeTree(BSTree* tree, DataDestroy dataDestroy)
{
    BST_FreeNode(tree->root, dataDestroy);//从根节点开始释放
    tree->root = NULL;
}

//前序打印函数的递归
void BST_PrevPrint(BSTNode* node, void (*func)(ElementType))
{
    if(node != NULL)
    {
        func(node->data);
        BST_PrevPrint(node->left, func);//
        BST_PrevPrint(node->right,func);
    }
}

//前序遍历
void BST_PrevTravel(BSTree* tree, void (*func)(ElementType))
{
    printf("Prev:\n");
    BST_PrevPrint(tree->root, func);
    printf("\n");
}

//中序打印函数的递归
void BST_MidPrint(BSTNode* node, void (*func)(ElementType))
{
    if(node != NULL)
    {
        BST_MidPrint(node->left, func);
        func(node->data);
        BST_MidPrint(node->right,func);
    }
}

//中序遍历
void BST_MidTravel(BSTree* tree, void (*func)(ElementType))
{
    printf("Mid:\n");
    BST_MidPrint(tree->root, func);
    printf("\n");
}

//后序打印函数的递归
void BST_PostPrint(BSTNode* node, void (*func)(ElementType))
{
    if(node != NULL)
    {      
        BST_PostPrint(node->left, func);
        BST_PostPrint(node->right, func);
        func(node->data);
    }
}

//后序遍历
void BST_PostTravel(BSTree* tree, void (*func)(ElementType))
{
    printf("Post:\n");
    BST_PostPrint(tree->root, func);
    printf("\n");
}

//层序遍历****************问题
void BST_SeqTravel(BSTree* tree, void (*PrintCall)(ElementType), void (*DataDestroy)(ElementType))
{
    //借助队列
    LQueue* lq = LQueue_Creat();
    if(tree->root != NULL)
        LQueue_Push(lq, tree->root);//根节点入队
    BSTNode* front;
    while(!LQueue_IsEmpty(lq))//队列不为空时
    {
        front = LQueue_GetFront(lq);//获取队首数据
        PrintCall(front->data);//打印
        LQueue_Pop(lq);//排出队首
        if(front->left != NULL)
            LQueue_Push(lq, front->left);//前队首左孩子入队
        if(front->right != NULL)
            LQueue_Push(lq, front->right);//前队首右孩子入队       
    }
    printf("\n");
    //LQueue_Destroy(lq, DataDestroy);
}



//查找元素所在节点
BSTNode* BST_findNode(BSTNode* node, ElementType element, int(*func)(ElementType, ElementType))
{
    if(node == NULL)
        return NULL;
    if(func(node->data, element) == 0) //通过回调函数比较节点数据元素是否相等，等则返回0
        return node;
    else if(func(node->data, element) < 0)//node->data中元素 < element中元素，返回1
        return BST_findNode(node->right, element, func);//返回1，向右子树往下搜索
    else
        return BST_findNode(node->left, element, func);//返回0，向左子树往下搜索
}

//查找值
BSTNode* BST_FindElement(BSTree* tree, ElementType element,int(*func)(ElementType, ElementType))
{
    return BST_findNode(tree->root, element, func);
}

//删除
void BST_DeleteElement(BSTree* tree, ElementType element, int(*func1)(ElementType, ElementType))
{
    BSTNode* targetNode = BST_FindElement(tree, element, func1);//查找元素所在节点,保存为targetNode
    if(targetNode == NULL)
       return;
    //左右子树均为空
    if(targetNode->left == NULL && targetNode->right == NULL)
    {
        if(targetNode->parent == NULL)//targetNode的父节点为根节点
            tree->root == NULL;
        else if(targetNode->parent->left == targetNode)
            targetNode->parent->left = NULL;
        else
            targetNode->parent->right = NULL;
        free(targetNode->data);
        free(targetNode);
    }
    //有左子树，右子树为空
    else if(targetNode->right == NULL)
    {
        if(targetNode->parent == NULL)
            tree->root = targetNode->left;
        else if(targetNode->parent->right == targetNode)
            targetNode->parent->right = targetNode->left;
        else
            targetNode->parent->left == targetNode->left;
        free(targetNode->data);
        free(targetNode);
    }
    //有右子树，左子树为空
    else if(targetNode->left == NULL)
    {
        if(targetNode->parent == NULL)
            tree->root = targetNode->right;
        else if(targetNode->parent->left == targetNode)
            targetNode->parent->left = targetNode->right;
        else
            targetNode->parent->right == targetNode->right;
        free(targetNode->data);
        free(targetNode);
    }
    //左右子树均存在
    else
    {
        //找targetNode右子树的最小值节点取代它的位置
        BSTNode* MinNode = targetNode->right;
        while(MinNode->left != NULL)//找目标节点右子树的最小值，即中序后继节点
            MinNode = MinNode->left;
            //***************************
        ElementType temp = targetNode->data;//交换目标节点和中序后继节点数据
        targetNode->data = MinNode->data;
        MinNode->data = temp;
        
        if(MinNode->parent == targetNode)//若中序后继节点的父节点就是目标节点
            targetNode->right = MinNode->right;//将中序后继节点的右孩子连接上目标节点的右孩子
        else                                       //中序后继节点的父节点不是目标节点       
            MinNode->parent->left = MinNode->right;//将中序后继节点的右孩子连接上中序后继节点父节点的的右孩子
        free(MinNode->data);//移除释放原中序后继节点
        free(MinNode);
    }
}

//求树某节点叶子数量
int BST_GetLeafNode(BSTNode* node)
{ 
    if(node == NULL)
        return 0;
    if(node->left == NULL && node->right ==NULL)
        return 1;
    int LeftNum = BST_GetLeafNode(node->left);
    int RightNum = BST_GetLeafNode(node->right);
    return LeftNum + RightNum;
}

//整颗树叶子数量
int BST_GetLeafNUm(BSTree* tree)
{
   return BST_GetLeafNode(tree->root);
}

